package com.cat.dynamicPlanning;

import java.util.Arrays;
import java.util.OptionalInt;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/combination-sum-iv/
 * @create 2025/8/26 15:47
 * @since JDK17
 */

public class Solution04 {
    static int[] dp = new int[1001];

    public int f1(int[] nums, int sum) {
        if (sum == 0) {
            return 1;
        }
        if (dp[sum] != -1) {
            return dp[sum];
        }
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum - nums[i] >= 0) {
                ans += f1(nums, sum - nums[i]);
            }
        }
        return dp[sum] = ans;
    }

    public int f2(int[] nums, int sum) {
        dp[sum] = 1;
        for (int i = sum - 1, n = nums.length; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }

        return dp[0];
    }

    public int combinationSum4(int[] nums, int target) {
        Arrays.fill(dp, 0);
        return f2(nums, target);
    }
}

